

/*
 * @lc app=leetcode.cn id=224 lang=cpp
 *
 * [224] 基本计算器
 *
 * https://leetcode-cn.com/problems/basic-calculator/description/
 *
 * algorithms
 * Hard (41.79%)
 * Likes:    716
 * Dislikes: 0
 * Total Accepted:    82.6K
 * Total Submissions: 197.5K
 * Testcase Example:  '"1 + 1"'
 *
 * 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 *
 * 注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：s = "1 + 1"
 * 输出：2
 *
 *
 * 示例 2：
 *
 *
 * 输入：s = " 2-1 + 2 "
 * 输出：3
 *
 *
 * 示例 3：
 *
 *
 * 输入：s = "(1+(4+5+2)-3)+(6+8)"
 * 输出：23
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= s.length <= 3 * 10^5
 * s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
 * s 表示一个有效的表达式
 * '+' 不能用作一元运算(例如， "+1" 和 "+(2 + 3)" 无效)
 * '-' 可以用作一元运算(即 "-1" 和 "-(2 + 3)" 是有效的)
 * 输入中不存在两个连续的操作符
 * 每个数字和运行的计算将适合于一个有符号的 32位 整数
 *
 *
 */

// @lc code=start
#include <iostream>
#include <stack>
using namespace std;
/* class Solution
{
public:
    int calculate(string s)
    {
        stack<int> nums;
        stack<char> operas;
        auto it = s.begin();
        int flag = 0;
        int changeflag = 0;
        int result = 0;
        int next = 0;
        bool canpop;
        while (it != s.end())
        {
            if (*it == ' ')
            {
                it++;
            }
            else if (*it == '+')
            {
                operas.push(*it);
                it++;
            }
            else if (*it == '-')
            {
                if (nums.empty())
                {
                    nums.push(0);
                }
                if (changeflag == 1)
                {
                    nums.push(0);
                }
                changeflag = 0;
                operas.push(*it);
                it++;
            }
            else if (*it == '(')
            {
                flag++;
                changeflag = 1;
                operas.push(*it);
                // if(operas.size()==1){
                //     flag--;
                // }
                it++;
            }
            else if (*it == ')')
            {
                flag--;
                changeflag = 0;
                operas.push(*it);
                it++;
            }
            else
            {
                int num = 0;
                while (*it >= '0' && *it <= '9')
                {
                    num = num * 10 + (*it - '0');
                    it++;
                }
                nums.push(num);
                changeflag = 0;
            }
            next = 0;
            while (next == 0)
            {
                if (operas.empty() == false)
                {
                    if (operas.top() == ')')
                    {
                        operas.pop();
                        canpop = true;
                    }
                    else if (operas.top() == '(' && canpop == true)
                    {
                        operas.pop();
                        canpop = false;
                    }
                    else if (operas.top() == '+' && nums.size() >= 2 + flag)
                    {
                        result = 0;
                        result += nums.top();
                        nums.pop();
                        result += nums.top();
                        nums.pop();
                        operas.pop();
                        nums.push(result);
                    }
                    else if (operas.top() == '-' && nums.size() >= 2 + flag)
                    {
                        result = 0;
                        result -= nums.top();
                        nums.pop();
                        result += nums.top();
                        nums.pop();
                        operas.pop();
                        nums.push(result);
                    }
                    else
                        next = 1;
                }
                else
                    next = 1;
            }
        }
        result = nums.top();
        return result;
    }
}; */

class Solution
{
public:
    void replace(string &s)
    {
        int pos = s.find(" ");
        while (pos != -1)
        {
            s.replace(pos, 1, "");
            pos = s.find(" ");
        }
    }
    int calculate(string s)
    {
        // 存放所有数字
        stack<int> nums;
        // 为了防止第一个数为负数，先往nums里加个0
        nums.push(0);
        // 将所有的空格去掉，调用内部函数
        replace(s);
        // 存放所有的操作
        stack<char> ops;
        int n=s.size();
        for(int i=0;i<n;i++){
            char c=s[i];
            if(c=='('){
                ops.push(c);
            }
            else if(c==')'){
                // 计算到最近一个左括号为止
                while(!ops.empty()){
                    char op=ops.top();
                    if(op!='('){
                        calc(nums,ops);
                    }
                    else {
                        ops.pop();
                        break;
                    }
                }
            }
            else{
                if(isdigit(c)){
                    int cur_num=0;
                    int j=i;
                    // 将从i位置开始后面的连续数字整体取出，加入nums
                    while(j<n&&isdigit(s[j]))
                    cur_num=cur_num*10+(s[j++]-'0');
                    // 注意上面的计算一定要有括号，否则有可能会溢出
                    nums.push(cur_num);
                    i=j-1;
                }
                else{
                    if(i>0&&(s[i-1]=='('||s[i-1]=='+'||s[i-1]=='-')){
                        nums.push(0);
                    }
                    // 有一个新操作要入栈时，先把栈内可以算的都算了
                    while(!ops.empty()&&ops.top()!='(')
                    calc(nums,ops);
                    ops.push(c);
                }
            }
        }
        while(!ops.empty())
        calc(nums,ops);
        return nums.top();
    }
    void calc(stack<int> &nums,stack<char> &ops){
        if(nums.size()<2||ops.empty()){
            return;
        }
        int b=nums.top();
        nums.pop();
        int a=nums.top();
        nums.pop();
        char op=ops.top();
        ops.pop();
        nums.push(op=='+'?a+b:a-b);
    }
};

// @lc code=end
